package org.example.algorithm.dp;

public class WaysToReachTargetSolution {
    private static final int MOD = (int) 1e9+7;

    public static void main(String[] args) {
        int target = 6;
        int[][] types = {{6,1},{3,2},{2,3}};
        WaysToReachTargetSolution solution = new WaysToReachTargetSolution();
        int res = solution.waysToReachTarget(target, types);
        System.out.println(res);
    }

    public int waysToReachTarget(int target, int[][] types) {
        int[] dp = new int[target+1];
        dp[0] = 1;
        for (int[] question: types) {
            int num = question[0];
            int score = question[1];
            for (int i=target;i>=1;i--) {
                for (int j=1;j<=num && j * score <= i;j++) {
                    dp[i] = (dp[i] + dp[i-score * j]) % MOD;
                }
            }
        }
        return dp[target];
    }
}
